#include <unordered_map>
#include <vector>
using namespace std;
int firstMissingPositive(vector<int> &nums) {
  unordered_map<int, int> count;
  int maxValue = -1;
  for (auto x : nums) {
    if (x > 0) {
      count[x]++;
      maxValue = max(maxValue, x);
    }
  }
  for (int i = 0; i < maxValue; ++i) {
    if (count.count(i) == 0) {
      return i;
    }
  }
  return 0;
}
// 使用数组就地hash
int firstMissingPositive_(vector<int> &nums) {
  for (int i = 0; i < nums.size(); ++i) {
    while (nums[i] <= nums.size() && nums[i] > 0 &&
           nums[i] != nums[nums[i] - 1]) {
      swap(nums[i], nums[nums[i] - 1]);
    }
    if (nums[i] > nums.size()) {
      nums[i] = -1;
    }
  }
  for (int i = 0; i < nums.size(); ++i) {
    if (nums[i] - 1 != i) {
      return i + 1;
    }
  }
  return nums.size() + 1;
}